import java.util.*;
import java.util.concurrent.*;

class MergeSort {
    static <T> void doMergeSort(T[] arr, int left, int right, Comparator<T> comparator){
        int mid = left+(right-left)/2;
        if(left<right){
            doMergeSort(arr, left, mid, comparator);
            doMergeSort(arr,mid+1, right, comparator);
            doMerge(arr, left, mid, right, comparator);
        }
    }

    static <T> void doMerge(T[] arr, int left, int mid, int right, Comparator<T> comparator) {
        T[] tmpArr = (T[]) new Object[right-left+1];
        int i= left;
        int j = mid+1;
        int k=0;
        while(i<=mid && j<=right){
            if(comparator.compare(arr[i],arr[j]) < 0){
                tmpArr[k++] = arr[i++];
            }else{
                tmpArr[k++] = arr[j++];
            }
        }
        while(i<=mid){
            tmpArr[k++] = arr[i++];
        }
        while(j<=right){
            tmpArr[k++] = arr[j++];
        }
        for (int l = 0; l < tmpArr.length; l++) {
            arr[left+l] = tmpArr[l];
        }
    }

    public static <T> void mergeSort(T[] arr, Comparator<T> comparator){
        doMergeSort(arr,0, arr.length-1, comparator);
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[10000];
        Random random = new Random();
        for (int i = 0; i < 10000; i++) {
            arr[i] = random.nextInt(10000);
        }
        long startTime = System.currentTimeMillis();
        mergeSort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        System.out.println(System.currentTimeMillis()-startTime);
    }
}



class QuickSort{
    public static <T> void doQuickSort(T[] arr, int low, int high, Comparator<T> comparator) {
        if(low >= high){
            return;
        }
        int i = low, j = high;
        T ptr, tmp = arr[low];
        while(i < j){
            while(comparator.compare(tmp,arr[j]) <= 0 && i < j){
                j--;
            }
            while(comparator.compare(tmp,arr[i]) >= 0 && i < j){
                i++;
            }
            if(i<j){
                ptr = arr[i];
                arr[i] = arr[j];
                arr[j] = ptr;
            }
        }
        ptr = arr[low];
        arr[low] = arr[i];
        arr[i] = ptr;
        doQuickSort(arr, low, i-1, comparator);
        doQuickSort(arr, i+1, high, comparator);
    }

    public static <T> void quickSort(T[] arr, Comparator<T> comparator) {doQuickSort(arr, 0, arr.length-1, comparator);}

    public static void main(String[] args) {
        Integer[] arr = new Integer[10000];
        Random random = new Random();
        for (int i = 0; i < 10000; i++) {
            arr[i] = random.nextInt(10000);
        }
        long startTime = System.currentTimeMillis();
        quickSort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        System.out.println(System.currentTimeMillis()-startTime);
    }
}

class insertSort{
    public static <T> void insertSort(T[] arr, Comparator<T> comparator){
        for (int j = 1; j < arr.length; j++) {
            for (int k = j - 1; k >= 0; k--) {
                if(comparator.compare(arr[k], arr[k+1]) <= 0) break;
                T tmp = arr[k+1];
                arr[k+1] = arr[k];
                arr[k] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[10000];
        Random random = new Random();
        for (int i = 0; i < 10000; i++) {
            arr[i] = random.nextInt(10000);
        }
        long startTime = System.currentTimeMillis();
        insertSort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        System.out.println(System.currentTimeMillis() - startTime);
        System.out.println(arr);
    }
}


class ShellSort{
    public static <T> void shellSort(T[] arr, Comparator<T> comparator){
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                for (int k = j - i; k >= 0; k -= i) {
                    if(comparator.compare(arr[k], arr[k+i]) <= 0) break;
                    T tmp = arr[k+i];
                    arr[k+i] = arr[k];
                    arr[k] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[100000];
        Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            arr[i] = random.nextInt(100000);
        }
        long startTime = System.currentTimeMillis();
        shellSort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        System.out.println(System.currentTimeMillis() - startTime);
        System.out.println(arr);
    }
}

class ParallelShellSort{
    private static ExecutorService threadPool = Executors.newFixedThreadPool(4);
    private static Semaphore sem = new Semaphore(0);

    static class doSort<T> implements Runnable{
        private final int start;
        private final int step;
        private final T[] arr;
        private final Comparator<T> comparator;

        public doSort(int start, int step, T[] arr, Comparator<T> comparator) {
            this.start = start;
            this.step = step;
            this.arr = arr;
            this.comparator = comparator;
        }

        @Override
        public void run() {
            for (int i = start + step; i < arr.length; i += step) {
                for (int j = i - step; j >= 0 ; j -= step) {
                    if(comparator.compare(arr[j], arr[j + step]) > 0){
                        T tmp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = tmp;
                    }
                    else{
                        break;
                    }
                }
            }
            sem.release();
        }
    }

    public static  <T> void sort(T[] arr, Comparator<T> comparator) throws InterruptedException {
        for (int i = arr.length / 2; i >= 1; i /= 2) {
            for (int j = 0; j < i; j++) {
                Thread tmpSortThread = new Thread(new doSort<>(j, i, arr, comparator));
                threadPool.execute(tmpSortThread);
            }
            sem.acquire(i);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Integer[] arr = new Integer[100000];
        Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            arr[i] = random.nextInt(100000);
        }
        long startTime = System.currentTimeMillis();
        ParallelShellSort.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        System.out.println(System.currentTimeMillis() - startTime);
        System.out.println(arr);
    }
}

class ParallelBlockSort{
    static class QuickSort<T> implements Runnable{
        final T[] arr;
        final int low;
        final int high;
        final Comparator comparator;

        public QuickSort(T[] arr, int low, int high, Comparator comparator) {
            this.arr = arr;
            this.low = low;
            this.high = high;
            this.comparator = comparator;
        }

        public void doQuickSort(int low, int high) {
            if(low >= high){
                return;
            }
            int i = low, j = high;
            T ptr, tmp = arr[low];
            while(i < j){
                while(comparator.compare(tmp,arr[j]) <= 0 && i < j){
                    j--;
                }
                while(comparator.compare(tmp,arr[i]) >= 0 && i < j){
                    i++;
                }
                if(i<j){
                    ptr = arr[i];
                    arr[i] = arr[j];
                    arr[j] = ptr;
                }
            }
            ptr = arr[low];
            arr[low] = arr[i];
            arr[i] = ptr;
            doQuickSort(low, i-1);
            doQuickSort(i+1, high);
        }

        @Override
        public void run() {
            doQuickSort(low, high);
            sem.release();
        }
    }

    static class Merge<T> implements Runnable{
        
        final T[] arr;
        final int start1;
        final int start2;
        final int end1;
        final int end2;
        final Comparator<T> comparator;

        public Merge(T[] arr, int start1, int start2, int end1, int end2, Comparator<T> comparator) {
            this.arr = arr;
            this.start1 = start1;
            this.start2 = start2;
            this.end1 = end1;
            this.end2 = end2;
            this.comparator = comparator;
        }

        @Override
        public void run() {
            T[] tmpArr = (T[]) new Object[end2 - start1 + 1];
            int i = start1, j = start2, ind = 0;
            for (; i <= end1 && j <= end2; ) {
                T iEle = arr[i], jEle = arr[j];
                if(comparator.compare(iEle, jEle) <= 0){
                    tmpArr[ind++] = iEle;
                    i++;
                }
                else {
                    tmpArr[ind++] = jEle;
                    j++;
                }
            }
            for (; i <= end1; ) {
                tmpArr[ind++] = arr[i++];
            }
            for (; j <= end2; ) {
                tmpArr[ind++] = arr[j++];
            }
            for (int k = 0; k < tmpArr.length; k++) {
                arr[start1 + k] = tmpArr[k];
            }
            sem.release();
        }
    }

    static final int threadNum = 4;
    static final ExecutorService threadPool = Executors.newFixedThreadPool(threadNum);
    static final Semaphore sem = new Semaphore(0);

    public static <T> void getSortArr(T[] arr, Comparator<T> comparator){
        int len = arr.length;
        int threadProcessLen = (len / threadNum) + (len % threadNum == 0 ? 0 : 1);
        for (int i = 0; i < len; i+=threadProcessLen) {
            threadPool.execute(new QuickSort<>(arr, i, Math.min(i + threadProcessLen - 1, len - 1), comparator));
        }
        try {
            sem.acquire(threadNum);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        for (int i = threadNum, j = threadProcessLen; i > 1; i /= 2, j *= 2) {
            for (int k = 0; k < len; k += 2*j) {
                threadPool.execute(new Merge<>(arr, k, k + j, k + j - 1, Math.min(k + 2 * j - 1, len - 1), comparator));
            }
            try {
                sem.acquire(i / 2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Integer[] arr = new Integer[1000000];
        Random random = new Random();
        for (int i = 0; i < 1000000; i++) {
            arr[i] = random.nextInt(1000000);
        }
        long startTime = System.currentTimeMillis();
        ParallelBlockSort.getSortArr(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
//        Arrays.parallelSort(arr, new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o1 - o2;
//            }
//        });
        System.out.println(System.currentTimeMillis() - startTime);
        System.out.println(arr);
    }

}


